Pada Januari 634, gabungan tentera Rom dan Parsi telah berjaya ditewaskan oleh jeneral Muslim, Khalid al-Walid dalam pertempuran Firaz. Pertempuran ini merupakan titik pertemuan pertama antara tentera Muslim dengan tentera Rom Timur serta kempen terakhir Khalid dalam ekspedisinya bertembung dengan tentera Parsi di Mesopotamia. Khalid merancang untuk melancarkan serangan ke dalam wilayah-wilayah Parsi tetapi beliau telah menerima utusan dari Khalifah Abu Bakar. Utusan tersebut memerintahkan Khalid untuk menamatkan serangannya ke atas Parsi sebaliknya pergi ke Syria untuk bertempur dengan tentera Rom. Jadi, Khalid bersama kontinjen kecilnya bersiap sedia untuk bergerak menuju ke barat.

Pada tahun 633, tentera Muslim telah menghantar empat pecahan pasukan untuk menyerang Palestin serta kawasan sekitar Laut Galilee, Sungai Jordan dan Laut Mati. Walaupun mereka beroleh kejayaan, serangan ke atas kawasan-kawasan tersebut tidak dapat dipertimbangkan. Khalifah Abu Bakar as-Siddiq telah mengarahkan Khalid bersama tentera-tenteranya untuk bergerak ke barat. Untuk memendekkan tempoh masa dan memintas pertahanan Rom, jeneral Muslim itu telah memilih laluan yang lebih ekstrem dan mencabar iaitu laluan yang terpencil melalui gurun Syria. Untuk memastikan kelangsungan kemaraan pasukannya, dilaporkan bahawa Khalid dengan bijaknya telah mengarahkan 20 ekor unta telah dipaksa untuk meminum kuantiti air yang besar supaya mereka dapat menggunakannya sebagai tangki simpanan buat sementara waktu. Unta tersebut kemudian telah disembelih sepanjang perjalanan semasa pasukan Khalid memerlukan bekalan. Pada masa yang sama, mereka juga dapat bekalan air daripada unta tersebut.

Selepas lima hari perjalanan yang melelahkan, tentera Muslim bersama kekuatan 9,000 orang berkumpul di Suwa. Kemudian, mereka mengalahkan kumpulan kecil tentera klien Arab Rom, Ghasan di Marj al-Rahit semasa mereka menyambut Hari Easter. Khalid telah membuktikan bahawa strateginya yang mustahil iaitu melalui laluan padang pasir telah berjaya meneutralkan pertahanan Byzantine di sempadan Arab. Kini, Khalid mengalihkan tumpuan ke kota Syria, Bosra di selatan sebelum pasukannya berjaya menguasai kota itu pada pertengahan bulan Julai 634. Pada masa itu, Maharaja Rom iaitu Heraclius yang berada di Emesa telah menghantar abangnya, Theodore bersama seorang jeneral Armenia, Vardan menuju ke Ajnadain. Ajnadain terletak di 25 batu dari tenggara Baitulmaqdis. Mereka telah berjaya mengumpulkan satu angkatan tentera yang besar. Perisik Muslim telah melaporkan pergerakan tentera musuh dan tentera Muslim telah berarak untuk bertembung dengan tentera Rom sekali gus mencetuskan Pertempuran Ajnadain.